package chapter7.graph;

/**
 * Created by lili on 2017/7/1.
 */
//【例7.5】  以Floyd算法求带权图每对顶点间的最短路径。

public class WeightedDirectedG7                  //带权有向图G7
{
    public static void main(String args[])
    {
        String[] vertices={"A","B","C","D"};
        Edge edges[]={new Edge(0,1,16), new Edge(0,2,57), new Edge(0,3,65),
                new Edge(1,2,11), new Edge(1,3,43),
                new Edge(2,0,39), new Edge(2,3,9),
                new Edge(3,0,22)};
//        AdjMatrixGraph<String> graph = new AdjMatrixGraph<String>(vertices, edges);
        AdjListGraph<String> graph = new AdjListGraph<String>(vertices, edges);
        System.out.print("带权有向图G7，"+graph.toString());
        graph.shortestPath();                    //调用Floyd算法求带权图每对顶点间的最短路径
    }
}
/*
程序运行结果如下：
带权有向图G7，顶点集合：(A, B, C, D)
邻接矩阵:
  0  16  57  65
  ∞  0  11  43
  39  ∞  0  9
  22  ∞  ∞  0

带权有向图G7，出边表：
(A：((0,1,16), (0,2,57), (0,3,65)),
B：((1,2,11), (1,3,43)),
C：((2,0,39), (2,3,9)),
D：((3,0,22)))

初值path数组
  -1  0  0  0
  -1  -1  1  1
  2  -1  -1  2
  3  -1  -1  -1
dist数组
  0  16  57  65
  ∞  0  11  43
  39  ∞  0  9
  22  ∞  ∞  0

以A作为中间顶点
(B,C)路径长度11，替换为(B,A),(A,C)路径长度100056？否
(B,D)路径长度43，替换为(B,A),(A,D)路径长度100064？否
(C,B)路径长度99999，替换为(C,A),(A,B)路径长度55？是，d21=55，p21=0
(C,D)路径长度9，替换为(C,A),(A,D)路径长度104？否
(D,B)路径长度99999，替换为(D,A),(A,B)路径长度38？是，d31=38，p31=0
(D,C)路径长度99999，替换为(D,A),(A,C)路径长度79？是，d32=79，p32=0
path数组
  -1  0  0  0
  -1  -1  1  1
  2  0  -1  2
  3  0  0  -1
dist数组
  0  16  57  65
  ∞  0  11  43
  39  55  0  9
  22  38  79  0

以B作为中间顶点
(A,C)路径长度57，替换为(A,B),(B,C)路径长度27？是，d02=27，p02=1
(A,D)路径长度65，替换为(A,B),(B,D)路径长度59？是，d03=59，p03=1
(C,A)路径长度39，替换为(C,A,B),(B,A)路径长度100054？否
(C,D)路径长度9，替换为(C,A,B),(B,D)路径长度98？否
(D,A)路径长度22，替换为(D,A,B),(B,A)路径长度100037？否
(D,A,C)路径长度79，替换为(D,A,B),(B,C)路径长度49？是，d32=49，p32=1
path数组
  -1  0  1  1
  -1  -1  1  1
  2  0  -1  2
  3  0  1  -1
dist数组
  0  16  27  59
  ∞  0  11  43
  39  55  0  9
  22  38  49  0

以C作为中间顶点
(A,B)路径长度16，替换为(A,B,C),(C,A,B)路径长度82？否
(A,B,D)路径长度59，替换为(A,B,C),(C,D)路径长度36？是，d03=36，p03=2
(B,A)路径长度99999，替换为(B,C),(C,A)路径长度50？是，d10=50，p10=2
(B,D)路径长度43，替换为(B,C),(C,D)路径长度20？是，d13=20，p13=2
(D,A)路径长度22，替换为(D,A,B,C),(C,A)路径长度88？否
(D,A,B)路径长度38，替换为(D,A,B,C),(C,A,B)路径长度104？否
path数组
  -1  0  1  2
  2  -1  1  2
  2  0  -1  2
  3  0  1  -1
dist数组
  0  16  27  36
  50  0  11  20
  39  55  0  9
  22  38  49  0

以D作为中间顶点
(A,B)路径长度16，替换为(A,B,C,D),(D,A,B)路径长度74？否
(A,B,C)路径长度27，替换为(A,B,C,D),(D,A,B,C)路径长度85？否
(B,C,A)路径长度50，替换为(B,C,D),(D,A)路径长度42？是，d10=42，p10=3
(B,C)路径长度11，替换为(B,C,D),(D,A,B,C)路径长度69？否
(C,A)路径长度39，替换为(C,D),(D,A)路径长度31？是，d20=31，p20=3
(C,D,A,B)路径长度55，替换为(C,D),(D,A,B)路径长度47？是，d21=47，p21=0
path数组
  -1  0  1  2
  3  -1  1  2
  3  0  -1  2
  3  0  1  -1
dist数组
  0  16  27  36
  42  0  11  20
  31  47  0  9
  22  38  49  0

每对顶点间的最短路径如下：
(A,B)长度为16
(A,B,C)长度为27
(A,B,C,D)长度为36
(B,C,D,A)长度为42
(B,C)长度为11
(B,C,D)长度为20
(C,D,A)长度为31
(C,D,A,B)长度为47
(C,D)长度为9
(D,A)长度为22
(D,A,B)长度为38
(D,A,B,C)长度为49


*/


